/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 基数;

/**
 * @Description 基数排序
 * （radix sort）属于“分配式排序”（distribution sort）
 * ，又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，
 * 将要排序的元素分配至某些“桶”中，达到排序的作用
 * 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
 * 基数排序(Radix Sort)是桶排序的扩展
 * 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
 * <p>
 * 基数排序是对传统桶排序的扩展，速度很快.
 * 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
 * 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，
 * 这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，
 * r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
 * 有负数的数组，我们不用基数排序来进行排序.
 * @Author 俊昭
 * @Date 2022/5/1
 */
public class Radix {
    /**
     * @param arr   要排序的数组
     * @param digit 数组中最大数的位数 如 1231 : digit=4
     * @return 排序好的数组
     * @description
     * @author 俊昭
     * @date 2022/5/2
     */
    public static int[] sort(int[] arr, int digit) {
        int times = 1;// 第几次排序
        int n = 1;// 执行排序的位 (个十百 1 10 100 )

        int x = 0;// 这个指针记录位置
        int[][] bucket = new int[10][arr.length];// 储存的大桶
        int[] eleCounts = new int[10];// 记录大桶中每个小桶存的数 个数
        while (times <= digit) {
            // 将数组按位存入桶中
            for (int j : arr) {
                int d = (j / n) % 10;// 算出这个数对应的位数的 数
                bucket[d][eleCounts[d]] = j;
                eleCounts[d]++;
            }
            // 从桶中取出
            for (int i = 0; i < 10; i++) {
                if (eleCounts[i] != 0) {
                    for (int j = 0; j < eleCounts[i]; j++) {
                        arr[x] = bucket[i][j];
                        x++;
                    }
                    eleCounts[i] = 0;// 重置
                }
            }
            x = 0;// 重置
            n *= 10;// 升一数位
            times++;// 下一次排序
        }
        return arr;

    }
}
